<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Mixing Styles
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora038.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora040.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Mixing Styles</H2> 
As we have mentioned, a language offering both functional and
imperative characteristics allows the programmer to choose the more
appropriate style for each part of the implementation of an algorithm.
One can indeed use both aspects in the same function. This is what we
will now illustrate. <BR>
<BR>
<A NAME="toc51"></A>
<H3> Closures and Side Effects</H3>
<A NAME="subsec-gensym"></A>The convention, when a function causes a side effect, is to treat it
as a procedure and to return the value <TT>()</TT>, of type
<I>unit</I>. Nevertheless, in some cases, it can be useful to cause
the side effect within a function that returns a useful value. We
have already used this mixture of the styles in the function
<TT>permute_pivot</TT> of quicksort.<BR>
<BR>
The next example is a symbol generator that creates a new symbol each
time that it is called. It simply uses a counter that is incremented
at every call. 


<PRE><BR># <B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE>;;<BR><CODE>val c : int ref = {contents=0}</CODE><BR># <B>let</B><CODE> </CODE>reset_symb<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>()<CODE> </CODE>-&gt;<CODE> </CODE>c<CODE>:=</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>val reset_symb : unit -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>new_symb<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>c<CODE>:=!</CODE>c<CODE>+</CODE><CODE>1</CODE><CODE> </CODE>;<CODE> </CODE>s<CODE>^</CODE><TT>(</TT>string_of_int<CODE> </CODE><CODE>!</CODE>c<TT>)</TT><CODE> </CODE>;;<BR><CODE>val new_symb : string -&gt; string = &lt;fun&gt;</CODE><BR># new_symb<CODE> </CODE><CODE>"VAR"</CODE><CODE> </CODE>;;<BR><CODE>- : string = "VAR1"</CODE><BR># new_symb<CODE> </CODE><CODE>"VAR"</CODE><CODE> </CODE>;;<BR><CODE>- : string = "VAR2"</CODE><BR># reset_symb<CODE> </CODE>()<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># new_symb<CODE> </CODE><CODE>"WAR"</CODE><CODE> </CODE>;;<BR><CODE>- : string = "WAR1"</CODE><BR># new_symb<CODE> </CODE><CODE>"WAR"</CODE><CODE> </CODE>;;<BR><CODE>- : string = "WAR2"</CODE><BR>

</PRE>
<BR>
<BR>
The reference <TT>c</TT> may be hidden from the rest of the program by
writing: <A NAME="subsec-gensymloc"></A> 


<PRE><BR># <B>let</B><CODE> </CODE><TT>(</TT>reset_s<CODE> </CODE><CODE>,</CODE><CODE> </CODE>new_s<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>let</B><CODE> </CODE>f1<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE>c<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>f2<CODE> </CODE>s<CODE> </CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE>c<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>c<CODE>+</CODE><CODE>1</CODE><CODE> </CODE>;<CODE> </CODE>s<CODE>^</CODE><TT>(</TT>string_of_int<CODE> </CODE><CODE>!</CODE>c<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><TT>(</TT>f1<CODE>,</CODE>f2<TT>)</TT><CODE> </CODE>;;<BR><CODE>val reset_s : unit -&gt; unit = &lt;fun&gt;</CODE><BR><CODE>val new_s : string -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
This declaration creates a pair of functions that share the 
variable <TT>c</TT>, which is local to this declaration. 
Using these two functions produces the same behavior as the previous
definitions. 


<PRE><BR># new_s<CODE> </CODE><CODE>"VAR"</CODE>;;<BR><CODE>- : string = "VAR1"</CODE><BR># new_s<CODE> </CODE><CODE>"VAR"</CODE>;;<BR><CODE>- : string = "VAR2"</CODE><BR># reset_s();;<BR><CODE>- : unit = ()</CODE><BR># new_s<CODE> </CODE><CODE>"WAR"</CODE>;;<BR><CODE>- : string = "WAR1"</CODE><BR># new_s<CODE> </CODE><CODE>"WAR"</CODE>;;<BR><CODE>- : string = "WAR2"</CODE><BR>

</PRE>
<BR>
<BR>
This example permits us to illustrate the way that closures are
represented. A closure may be considered as a pair containing the code
(that is, the <B>function</B> part) as one component and the local
envoronment containing the values of the free variables of the
function. Figure&nbsp;<A HREF="book-ora039.html#fig-gensym">4.1</A> shows the memory representation of the
closures <TT>reset_s</TT> and <TT>new_s</TT>.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora006.gif">
<BR>
<BR>
<DIV ALIGN=center>Figure 4.1: Memory representation of closures.</DIV><BR>

<A NAME="fig-gensym"></A>
</DIV>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>These two closures share the same environment, containing the value of
<TT>c</TT>. When either one modifies the reference <TT>c</TT>, it
modifies the contents of an area of memory that is shared with the
other closure.<BR>
<BR>
<A NAME="toc52"></A>
<H3> Physical Modifications and Exceptions</H3>
Exceptions make it possible to escape from situations in which the
computation cannot proceed. In this case, an exception handler allows
the calculation to continue, knowing that one branch has failed. The
problem with side effects comes from the state of the modifiable data
when the exception was raised. One cannot be sure of this state if
there have been physical modifications in the branch of the
calculation that has failed. <BR>
<BR>
Let us define the increment function <TT>(++)</TT> analogous to the
operator in C:


<PRE><BR># <B>let</B><CODE> </CODE><TT>(</TT><CODE>++</CODE><TT>)</TT><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE>:=!</CODE>x<CODE>+</CODE><CODE>1</CODE>;<CODE> </CODE>x;;<BR><CODE>val ++ : int ref -&gt; int ref = &lt;fun&gt;</CODE><BR>

</PRE>

The following example shows a little computation where division by
zero occurs together with 


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>2</CODE>;;<BR><CODE>val x : int ref = {contents=2}</CODE><BR><CODE>(* 1 *)</CODE><BR># <CODE>!</CODE><TT>(</TT><TT>(</TT><CODE>++</CODE><TT>)</TT><CODE> </CODE>x<TT>)</TT><CODE> </CODE><CODE>*</CODE><CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>/</CODE><CODE>0</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>Uncaught exception: Division_by_zero</CODE><BR># x;;<BR><CODE>- : int ref = {contents=2}</CODE><BR><CODE>(* 2 *)</CODE><BR># <TT>(</TT><CODE>1</CODE><CODE>/</CODE><CODE>0</CODE><TT>)</TT><CODE> </CODE><CODE>*</CODE><CODE> </CODE><CODE>!</CODE><TT>(</TT><TT>(</TT><CODE>++</CODE><TT>)</TT><CODE> </CODE>x<TT>)</TT><CODE> </CODE>;;<BR><CODE>Uncaught exception: Division_by_zero</CODE><BR># x;;<BR><CODE>- : int ref = {contents=3}</CODE><BR>

</PRE>

The variable <TT>x</TT> is not modified during the computation of
the expression in (*1*), while it is modified in the computation of
(*2*). Unless one saves the initial values, the form <B>try ..
with ..</B> must not have a <B>with ..</B> part that depends on
modifiable variables implicated in the expression that raised the
exception. <BR>
<BR>
<A NAME="toc53"></A>
<H3> Modifiable Functional Data Structures</H3> In functional
programming a program (in particular, a function expression) may also
serve as a data object that may be manipulated, and one way to see
this is to write association lists in the form of function
expressions. In fact, one may view association lists of type
<I>('a * 'b) list</I> as partial functions taking a key chosen from
the set <I>'a</I> and returning a value in the set of associated
values <I>'b</I>.
Each association list is then a function of type <I>'a -&gt; 'b</I>.<BR>
<BR>
The empty list is the everywhere undefined function, which one
simulates by raising an exception:


<PRE><BR># <B>let</B><CODE> </CODE>nil_assoc<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>Not_found<CODE> </CODE>;;<BR><CODE>val nil_assoc : 'a -&gt; 'b = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
We next write the function <TT>add_assoc</TT> which adds an element
to a list, meaning that it extends the function for a new entry:


<PRE><BR># <B>let</B><CODE> </CODE>add_assoc<CODE> </CODE><TT>(</TT>k<CODE>,</CODE>v<TT>)</TT><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>k<CODE> </CODE><B>then</B><CODE> </CODE>v<CODE> </CODE><B>else</B><CODE> </CODE>l<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val add_assoc : 'a * 'b -&gt; ('a -&gt; 'b) -&gt; 'a -&gt; 'b = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>add_assoc<CODE> </CODE><TT>(</TT><CODE>'1'</CODE><CODE>,</CODE><CODE> </CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>add_assoc<CODE> </CODE><TT>(</TT><CODE>'2'</CODE><CODE>,</CODE><CODE> </CODE><CODE>2</CODE><TT>)</TT><CODE> </CODE>nil_assoc<TT>)</TT><CODE> </CODE>;;<BR><CODE>val l : char -&gt; int = &lt;fun&gt;</CODE><BR># l<CODE> </CODE><CODE>'2'</CODE><CODE> </CODE>;;<BR><CODE>- : int = 2</CODE><BR># l<CODE> </CODE><CODE>'x'</CODE><CODE> </CODE>;;<BR><CODE>Uncaught exception: Not_found</CODE><BR>

</PRE>
<BR>
<BR>
We may now re-write the function <TT>mem_assoc</TT>:


<PRE><BR># <B>let</B><CODE> </CODE>mem_assoc<CODE> </CODE>k<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>try</B><CODE> </CODE><CODE> </CODE><TT>(</TT>l<CODE> </CODE>k<TT>)</TT><CODE> </CODE>;<CODE> </CODE><B>true</B><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE><CODE> </CODE>Not_found<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE>;;<BR><CODE>val mem_assoc : 'a -&gt; ('a -&gt; 'b) -&gt; bool = &lt;fun&gt;</CODE><BR># mem_assoc<CODE> </CODE><CODE>'2'</CODE><CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>- : bool = true</CODE><BR># mem_assoc<CODE> </CODE><CODE>'x'</CODE><CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>- : bool = false</CODE><BR>

</PRE>
<BR>
<BR>
By contrast, writing a function to remove an element from a list is
not trivial, because one no longer has access to the values captured
by the closures. To accomplish the same purpose we mask the former
value by raising the exception 
<TT>Not_found</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>rem_assoc<CODE> </CODE>k<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>x<CODE>=</CODE>k<CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE>Not_found<CODE> </CODE><B>else</B><CODE> </CODE>l<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val rem_assoc : 'a -&gt; ('a -&gt; 'b) -&gt; 'a -&gt; 'b = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>rem_assoc<CODE> </CODE><CODE>'2'</CODE><CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>val l : char -&gt; int = &lt;fun&gt;</CODE><BR># l<CODE> </CODE><CODE>'2'</CODE><CODE> </CODE>;;<BR><CODE>Uncaught exception: Not_found</CODE><BR>

</PRE>
<BR>
<BR>
Clearly, one may also create references and work by side effect on
such values. However, one must take some care.


<PRE><BR># <B>let</B><CODE> </CODE>add_assoc_again<CODE> </CODE><TT>(</TT>k<CODE>,</CODE>v<TT>)</TT><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>l<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>x<CODE>=</CODE>k<CODE> </CODE><B>then</B><CODE> </CODE>v<CODE> </CODE><B>else</B><CODE> </CODE><CODE>!</CODE>l<CODE> </CODE>x<TT>)</TT><CODE> </CODE>;;<BR><CODE>val add_assoc_again : 'a * 'b -&gt; ('a -&gt; 'b) ref -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The resulting value for <TT>l</TT> is a function that points at itself
and therefore loops. This annoying side effect is due to the fact that
the dereferencing <CODE>!</CODE>l is within the scope of the closure
<B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;. The value of <CODE>!</CODE>l is not evaluated
during compilation, but at run-time. At that time, <TT>l</TT> points
to the value that has already been modified by <TT>add_assoc</TT>. We
must therefore correct our definition using the closure created by our
original definition of <TT>add_assoc</TT>:


<PRE><BR># <B>let</B><CODE> </CODE>add_assoc_again<CODE> </CODE><TT>(</TT>k<CODE>,</CODE><CODE> </CODE>v<TT>)</TT><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>l<CODE> </CODE><CODE>:=</CODE><CODE> </CODE>add_assoc<CODE> </CODE><TT>(</TT>k<CODE>,</CODE><CODE> </CODE>v<TT>)</TT><CODE> </CODE><CODE>!</CODE>l<CODE> </CODE>;;<BR><CODE>val add_assoc_again : 'a * 'b -&gt; ('a -&gt; 'b) ref -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>nil_assoc<CODE> </CODE>;;<BR><CODE>val l : ('_a -&gt; '_b) ref = {contents=&lt;fun&gt;}</CODE><BR># add_assoc_again<CODE> </CODE><TT>(</TT><CODE>'1'</CODE><CODE>,</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># add_assoc_again<CODE> </CODE><TT>(</TT><CODE>'2'</CODE><CODE>,</CODE><CODE>2</CODE><TT>)</TT><CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># <CODE>!</CODE>l<CODE> </CODE><CODE>'1'</CODE><CODE> </CODE>;;<BR><CODE>- : int = 1</CODE><BR># <CODE>!</CODE>l<CODE> </CODE><CODE>'x'</CODE><CODE> </CODE>;;<BR><CODE>Uncaught exception: Not_found</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc54"></A>
<H3> Lazy Modifiable Data Structures</H3>
<A NAME="subsec-paresse"></A>
<A NAME="@concepts111"></A>Combining imperative characteristics with a functional language
produces good tools for implementing computer languages. In this
subsection, we will illustrate this idea by implementing data
structures with deferred evaluation. A data structure of this kind is
not completely evaluated. Its evaluation progresses according to the
use made of it. <BR>
<BR>
Deferred evaluation, which is often used in purely functional
languages, is simulated using function values, possibly modifiable.
There are at least two purposes for manipulating incompletely
evaluated data structures: first, so as to calculate only what is
effectively needed in the computation; and second, to be able to work
with potentially infinite data structures. <BR>
<BR>
We define the type <TT>vm</TT>, whose members contain either an
already calculated value (constructor <TT>Imm</TT>) or else a value to
be calculated (constructor <TT>Deferred</TT>):


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Imm<CODE> </CODE><B>of</B><CODE> </CODE><I>'a</I><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Deferred<CODE> </CODE><B>of</B><CODE> </CODE><TT>(</TT>unit<CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><TT>)</TT>;;<BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>vm<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<B>mutable</B><CODE> </CODE>c<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>v<CODE> </CODE>};;<BR>

</PRE>
<BR>
<BR>
A computation is deferred by encapsulating it in a closure. The
evaluation function for deferred values must return the value if it
has already been calculated, and otherwise, if the value is not
already calculated, it must evaluate it and then store the result.
 

<PRE><BR># <B>let</B><CODE> </CODE>eval<CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>e<CODE>.</CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>Imm<CODE> </CODE>a<CODE> </CODE>-&gt;<CODE> </CODE>a<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Deferred<CODE> </CODE>f<CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>u<CODE> </CODE><CODE>=</CODE><CODE> </CODE>f<CODE> </CODE>()<CODE> </CODE><B>in</B><CODE> </CODE>e<CODE>.</CODE>c<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Imm<CODE> </CODE>u<CODE> </CODE>;<CODE> </CODE>u<CODE> </CODE>;;<BR><CODE>val eval : 'a vm -&gt; 'a = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="@concepts112"></A>
<A NAME="@concepts113"></A>
The operations of deferring evaluation and activating it are also
called freezing and thawing a value.<BR>
<BR>
We could also write the conditional control structure in the form of a
function: 


<PRE><BR># <B>let</B><CODE> </CODE>if_deferred<CODE> </CODE>c<CODE> </CODE>e1<CODE> </CODE>e2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>eval<CODE> </CODE>c<CODE> </CODE><B>then</B><CODE> </CODE>eval<CODE> </CODE>e1<CODE> </CODE><B>else</B><CODE> </CODE>eval<CODE> </CODE>e2;;<BR><CODE>val if_deferred : bool vm -&gt; 'a vm -&gt; 'a vm -&gt; 'a = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Here is how to use it in a recursive function such as factorial: 


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>facr<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>if_deferred<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{c<CODE>=</CODE>Deferred<TT>(</TT><B>fun</B><CODE> </CODE>()<CODE> </CODE>-&gt;<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><TT>)</TT>}<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{c<CODE>=</CODE>Deferred<TT>(</TT><B>fun</B><CODE> </CODE>()<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>1</CODE><TT>)</TT>}<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{c<CODE>=</CODE>Deferred<TT>(</TT><B>fun</B><CODE> </CODE>()<CODE> </CODE>-&gt;<CODE> </CODE>n<CODE>*</CODE><TT>(</TT>facr<TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><TT>)</TT>};;<BR><CODE>val facr : int -&gt; int = &lt;fun&gt;</CODE><BR># facr<CODE> </CODE><CODE>5</CODE>;;<BR><CODE>- : int = 120</CODE><BR>

</PRE>
<BR>
<BR>
The classic form of <B>if</B> can not be written in the form of a
function. In fact, if we define a function <TT>if_function</TT> this
way: 


<PRE><BR># <B>let</B><CODE> </CODE>if_function<CODE> </CODE>c<CODE> </CODE>e1<CODE> </CODE>e2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>if</B><CODE> </CODE>c<CODE> </CODE><B>then</B><CODE> </CODE>e1<CODE> </CODE><B>else</B><CODE> </CODE>e2;;<BR><CODE>val if_function : bool -&gt; 'a -&gt; 'a -&gt; 'a = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
then the three arguments of <TT>if_function</TT> are evaluated at the
time they are passed to the function. So the function <TT>fact</TT>
loops, because the recursive call fact<TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT> is always
evaluated, even when <TT>n</TT> has the value <TT>0</TT>. 


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>fact<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>if_function<CODE> </CODE><TT>(</TT>n<CODE>=</CODE><CODE>0</CODE><TT>)</TT><CODE> </CODE><CODE>1</CODE><CODE> </CODE><TT>(</TT>n<CODE>*</CODE>fact<TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val fact : int -&gt; int = &lt;fun&gt;</CODE><BR># fact<CODE> </CODE><CODE>5</CODE><CODE> </CODE>;;<BR><CODE>Stack overflow during evaluation (looping recursion?).</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Module <TT>Lazy</TT></H4>
<A NAME="@fonctions132"></A>
<A NAME="@fonctions133"></A> 
The implementation difficulty for frozen values is due to the conflict
between the eager evaluation strategy of Objective CAML and the need to
leave expressions unevaluated. Our attempt to redefine the conditional
illustrated this. More generally, it is impossible to write a
function that freezes a value in producing an object of type
<I>vm</I>: 


<PRE><BR># <B>let</B><CODE> </CODE>freeze<CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Deferred<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>()<CODE> </CODE>-&gt;<CODE> </CODE>e<TT>)</TT><CODE> </CODE>};;<BR><CODE>val freeze : 'a -&gt; 'a vm = &lt;fun&gt;</CODE><BR>

</PRE>

When this function is applied to arguments, the Objective CAML evaluation
strategy evaluates the expression <TT>e</TT> passed as argument before
constructing the closure <B>fun</B><CODE> </CODE>()<CODE> </CODE>-&gt;<CODE> </CODE>e. The next example
shows this: 


<PRE><BR># freeze<CODE> </CODE><TT>(</TT>print_string<CODE> </CODE><CODE>"trace"</CODE>;<CODE> </CODE>print_newline();<CODE> </CODE><CODE>4</CODE><CODE>*</CODE><CODE>5</CODE><TT>)</TT>;;<BR><CODE>trace</CODE><BR><CODE>- : int vm = {c=Deferred &lt;fun&gt;}</CODE><BR>

</PRE>
<BR>
<BR>
This is why the following syntactic form was introduced.


<H3> Syntax </H3> <HR>


<B>lazy</B> <I>expr</I>



<HR>

<BR>
<BR>


<H3> Warning </H3> <HR>

This form is a language extension that may evolve in future versions. 


<HR>


<A NAME="@fonctions134"></A>
<A NAME="@fonctions135"></A>
<A NAME="@fonctions136"></A><BR>
<BR>
When the keyword <B>lazy</B> is applied to an expression, it
constructs a value of a type declared in the module <TT>Lazy</TT>: 


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>lazy</B><CODE> </CODE><TT>(</TT>print_string<CODE> </CODE><CODE>"Hello"</CODE>;<CODE> </CODE><CODE>3</CODE><CODE>*</CODE><CODE>4</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val x : int Lazy.status ref = {contents=Lazy.Delayed &lt;fun&gt;}</CODE><BR>

</PRE>
<BR>
<BR>
The expression <TT>(</TT>print_string<CODE> </CODE><CODE>"Hello"</CODE><TT>)</TT> has not been
evaluated, because no message has been printed. The function
<TT>force</TT> of module <TT>Lazy</TT> allows one to force evaluation: 


<PRE><BR># Lazy.force<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>Hello- : int = 12</CODE><BR>

</PRE>

Now the value <TT>x</TT> has altered:


<PRE><BR># x<CODE> </CODE>;;<BR><CODE>- : int Lazy.t = {contents=Lazy.Value 12}</CODE><BR>

</PRE>

It has become the value of the expression that had been frozen, namely
<CODE>1</CODE><CODE>2</CODE>. <BR>
<BR>
For another call to the function <TT>force</TT>, it's enough to return
the value already calculated:


<PRE><BR># Lazy.force<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>- : int = 12</CODE><BR>

</PRE>

The string <CODE>"Hello"</CODE> is no longer prefixed.<BR>
<BR>

<H4> ``Infinite'' Data Structures</H4>
The second reason to defer evaluation is to be able to construct
potentially infinite data structures such as the set of natural
numbers. Because it might take a long time to construct them all, the
idea here is to compute only the first one and to know how to pass to
the next element.<BR>
<BR>
We define a generic data structure <I>'a enum</I> which will allow
us to enumerate the elements of a set. 
<A NAME="C-Styles-ens"></A>


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>enum<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>i<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I>;<CODE> </CODE>f<CODE> </CODE><CODE>:</CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type 'a enum = { mutable i: 'a; f: 'a -&gt; 'a }</CODE><BR># <B>let</B><CODE> </CODE>next<CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>e<CODE>.</CODE>i<CODE> </CODE><B>in</B><CODE> </CODE>e<CODE>.</CODE>i<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><TT>(</TT>e<CODE>.</CODE>f<CODE> </CODE>e<CODE>.</CODE>i<TT>)</TT><CODE> </CODE>;<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val next : 'a enum -&gt; 'a = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Now we can get the set of natural numbers by instantiating the fields
of this structure:


<PRE><BR># <B>let</B><CODE> </CODE>nat<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>f<CODE>=</CODE><B>fun</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE>};;<BR><CODE>val nat : int enum = {i=0; f=&lt;fun&gt;}</CODE><BR># next<CODE> </CODE>nat;;<BR><CODE>- : int = 0</CODE><BR># next<CODE> </CODE>nat;;<BR><CODE>- : int = 1</CODE><BR># next<CODE> </CODE>nat;;<BR><CODE>- : int = 2</CODE><BR>

</PRE>

Another example gives the elements of the Fibonnacci sequence, which
has the definition:
<DIV ALIGN=center><TABLE CELLSPACING=0 CELLPADDING=0>
<TR VALIGN=middle><TD NOWRAP><FONT FACE=symbol>
�<BR>�<BR>�</FONT></TD>
<TD NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><I>u</I><SUB><FONT SIZE=2>0</FONT></SUB> = 1</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><I>u</I><SUB><FONT SIZE=2>1</FONT></SUB> = 1</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><I>u</I><SUB><FONT SIZE=2><I>n</I>+2</FONT></SUB> = <I>u</I><SUB><FONT SIZE=2><I>n</I></FONT></SUB> + <I>u</I><SUB><FONT SIZE=2><I>n</I>+1</FONT></SUB></TD>
</TR></TABLE></TD>
</TR></TABLE></DIV>
The function to compute the successor must take account of the current
value, (<I>u</I><SUB><FONT SIZE=2><I>n</I>-1</FONT></SUB>), but also of the preceding one (<I>u</I><SUB><FONT SIZE=2><I>n</I>-2</FONT></SUB>). For
this, we use the state <TT>c</TT> in the following closure: 


<PRE><BR># <B>let</B><CODE> </CODE>fib<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>let</B><CODE> </CODE>fx<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>fun</B><CODE> </CODE>v<CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>!</CODE>c<CODE> </CODE><CODE>+</CODE><CODE> </CODE>v<CODE> </CODE><B>in</B><CODE> </CODE>c<CODE>:=</CODE>v<CODE> </CODE>;<CODE> </CODE>r<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>{<CODE> </CODE>i<CODE>=</CODE><CODE>1</CODE><CODE> </CODE>;<CODE> </CODE>f<CODE>=</CODE>fx<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val fib : int enum = {i=1; f=&lt;fun&gt;}</CODE><BR># <B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE> </CODE><B>do</B><CODE> </CODE><CODE> </CODE>print_int<CODE> </CODE><TT>(</TT>next<CODE> </CODE>fib<TT>)</TT>;<CODE> </CODE>print_string<CODE> </CODE><CODE>"  "</CODE><CODE> </CODE><B>done</B><CODE> </CODE>;;<BR><CODE>1  1  2  3  5  8  13  21  34  55  89  - : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
<HR>
<A HREF="book-ora038.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora040.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
